package com.leetcode.双周赛.第45场;

/**
 * @author: xiaomi
 * @date: 2021/2/6
 * @description: 5659. 删除字符串两端相同字符后的最短长度
 * https://leetcode-cn.com/contest/biweekly-contest-45/problems/minimum-length-of-string-after-deleting-similar-ends/
 */
public class B_5659_删除字符串两端相同字符后的最短长度 {

    public static void main(String[] args) {
        String s = "ca";
//        s = "cabaabac";
        s = "aabccabba";
        s = "bbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbccbcbcbccbbabbb";

        B_5659_删除字符串两端相同字符后的最短长度 action = new B_5659_删除字符串两端相同字符后的最短长度();
        int res = action.minimumLength(s);
        System.out.println("res = " + res);

    }

    /**
     * 这道题就是题意理解有问题，总的来说这次周赛难度不大，如果我会 DP 的话。
     * @param s
     * @return
     */
    public int minimumLength(String s) {
        //1.边界判断
        int len = s.length();
        if (len < 2) {
            return len;
        }
        char[] tempArr = s.toCharArray();
        //
        while (len > 1 && (tempArr = process(tempArr)).length < len) {
            len = tempArr.length;
        }

        return len;
    }

    private char[] process(char[] arr) {
        if (arr[0] != arr[arr.length - 1]) {
            return arr;
        }
        //此时 首尾相等
        int begin = 0;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] != arr[begin]) {
                begin = i;
                break;
            }
        }
        if (begin == 0) {
            return new char[0];
        }
        int end = arr.length - 1;
        //这里边界依然有问题
        //此时 begin 就是 ) 的索引位置
        for (int i = end - 1; i > begin; i--) {
            if (arr[i] != arr[end]) {
                end = i;
                break;
            }
        }
        if (end == arr.length - 1) {
            end--;
        }
        int l = end - begin + 1;
        char[] chars = new char[l];
        System.arraycopy(arr, begin, chars, 0, l);
        return chars;
    }
}
